home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / node_pq.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  2.2 KB  |  75 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.11 Node priority queues (node\_pq)}
  4.  
  5. \decl node\_pq I 
  6.  
  7. {\bf 1. Definition}
  8.  
  9. An instance $Q$ of the parameterized data type \name\ is a partial 
  10. function from the nodes of a graph $G$ to the linearly ordered type $I$.
  11.  
  12. \bigskip
  13. {\bf 2. Creation}
  14.  
  15. \create Q (G)
  16.  
  17. creates an instance $Q$ ot type \name\ for the nodes of graph $G$
  18. with $dom(Q)=\emptyset$.
  19.  
  20.  
  21.  
  22. \bigskip
  23. {\bf 3. Operations} 
  24.  
  25. \medskip
  26. \+\op void insert {node\ v,\ I\ i}    
  27.                         {adds the node $v$ with information $i$ to}
  28. \+\nop                  {\var. \precond $v\not\in dom(Q)$.}
  29. \smallskip
  30. \+\op I    inf {node\ v}
  31.                         {returns information of node $v$.}
  32. \smallskip
  33. \+\op bool member {node\ v}
  34.                         {returns true if $v$ in \var, false otherwise.}
  35. \smallskip
  36. \+\op void decrease\_inf {node\ v,\ I\ i} 
  37.                         {makes $i$ the new information of node $v$}
  38. \+\nop                  {(\precond $i \le Q(v)$).}
  39. \smallskip
  40. \+\op node find\_min {}          
  41.                         {returns a node with the minimal }
  42. \+\nop                  {information(nil if \var\ is empty)}
  43. \smallskip
  44. \+\op void del {node\ v}           
  45.                         {removes the node $v$ from \var }
  46. \smallskip
  47. \+\op node del\_min {}             
  48.                         {removes a node with the minimal}
  49. \+\nop                  {information from \var\ and returns it}
  50. \+\nop                  {(nil if \var\ is empty)}
  51. \smallskip
  52. \+\op int      size  {}
  53.                         {returns $|dom(Q)|$. }
  54. \smallskip
  55. \+\op void clear {}                 
  56.                         {makes $Q$ the empty node priority queue.}
  57. \smallskip
  58.  
  59. \+\op bool  empty {}                 
  60.                         {returns true if \var\ is the empty node}
  61. \+\nop                  {priority queue, false otherwise.}
  62.  
  63.  
  64. \bigskip
  65. {\bf 4. Implementation}
  66.  
  67. Node priority queues are implemented by fibonacci heaps and node arrays.
  68. Operations insert, del\_node, del\_min take time $O(\log n)$, find\_min, 
  69. decrease\_inf, empty take time $O(1)$ and clear takes time $O(m)$, where 
  70. $m$ is the size of $Q$. The space requirement is $O(n)$, where $n$ is the 
  71. number of nodes of $G$.
  72.  
  73. \vfill\eject
  74.  
  75.